#ifndef SANDBOX_SDK_UTIL_OBSTACK_ALLOCATOR_HPP
#define SANDBOX_SDK_UTIL_OBSTACK_ALLOCATOR_HPP

#include "internals.hpp"

namespace sandbox
{
	namespace sdk 
	{
		/**
		 * \brief template <size_t SIZE> class RawObstackAllocator;
		 *        An allocator, which can quickly allocate chunks of 
		 *        size 'SIZE' in temporary storage
		 * 
		 * RawObstackAllocator is movable, noncopyable allocator
		 * useful to quicky allocate temporary lists and remove them
		 * all at destruction of the allocator object.
		 * All allocated memory is freed only on destruction of the 
		 * allocator
		 */
		template <size_t CHKSIZE, size_t SIZE, size_t ALIGN> class RawObstackAllocator 
		{
		public:
			enum {allocation_unit=::sandbox::sdk::detail::sizealign(SIZE,ALIGN)};
			/**
			 * Creates an allocator object and preserves appropriate 
			 * amount of memory for temporary memory pool
			 */
			RawObstackAllocator(){
				m_head=::sandbox::sdk::aligned::alloc(CHKSIZE);
				m_index=NULL;
				m_head_pos=0;
				m_index_pos=1;
			}
			/**
			 * Destroyes allocator and frees all memory previously 
			 * allocated by this allocator
			 */
			~RawObstackAllocator() throw(){
				if(m_head!=NULL)::sandbox::sdk::aligned::free(m_head);
				void ** iterator=m_index;
				size_t  ientries=m_index_pos;
				while(iterator!=NULL){
					//remove all entries in this chunk	
					for(int i=1; i<ientries;++i)
						::sandbox::sdk::aligned::free(iterator[i]);
					void *prev=(void*)iterator;
					iterator=(void**)iterator[0];
					ientries=index_chunk_size/sizeof(void*);
					::sandbox::sdk::aligned::free(prev);
				}
			}
			//allocator is trivially movable
			RawObstackAllocator(RawObstackAllocator&& src) throw()
			{
				m_head=src.m_head;
				m_index=src.m_index;
				m_head_pos=src.m_head_pos;
				src.m_head=NULL;
				src.m_index=NULL;
				src.m_head_pos=0;
			}
			RawObstackAllocator& operator =(RawObstackAllocator&& src) throw()
			{
				m_head=src.m_head;
				m_index=src.m_index;
				m_head_pos=src.m_head_pos;
				src.m_head=NULL;
				src.m_index=NULL;
				src.m_head_pos=0;
				return *this;
			}
			/**
			 * allocates and returns address of uninitialized memory suitable
			 * for object of size SIZE. address will be aligned on appropriate 
			 * boundary for SIZE<=16, SIZE=32,64, or on 16 byte boundary for
			 * all SIZES>16(except 32 and 64).
			 * @return address of newly allocated block. Will be freed on 
			 * destruction of allocator. No destructors will be called!
			 */
			void* allocate(size_t num) 
			{
				assert(m_head_pos<=chunk_limit);
				assert(m_index_pos<=index_chunk_size/sizeof(void*));

				if(num*allocation_unit>chunk_limit)throw std::bad_alloc();				
				//last chunk is full?
				if(chunk_limit-m_head_pos < num*allocation_unit)
				{
					//last index is full too?
					if(m_index_pos==index_chunk_size/sizeof(void*))
					{
						void ** newchk=(void**)::sandbox::sdk::aligned::alloc(index_chunk_size);//may throw
						newchk[0]=m_index;
						m_index=newchk;
						m_index_pos=1;
					}
					void * newchk=::sandbox::sdk::aligned::alloc(CHKSIZE);//may throw
					m_index[m_index_pos++]=m_head;
					m_head=newchk;
					m_head_pos=0;
				}
				void* result=m_head+m_head_pos;
				m_head_pos+=allocation_unit*num;
				return result;
			}
			void deallocate(void *, size_t)const{}
			
			size_t max_size()const
			{
				return chunk_limit/SIZE;
				//size_t chkfree=m_head_pos==chunk_limit ? chunk_limit : (m_head_pos-chunk_limit);
				//return chkfree/allocation_unit;
			}
		private:
			enum {index_chunk_size=4096};
			enum {chunk_limit=CHKSIZE - (CHKSIZE % allocation_unit)};
			//allocator is not copyable
			RawObstackAllocator(const RawObstackAllocator&)=delete;
			RawObstackAllocator& operator =(const RawObstackAllocator&)=delete;
			void         * m_head;
			void        ** m_auxillary;
			size_t         m_head_pos;
			size_t         m_index_pos;
		};
	}
}

#endif //SANDBOX_SDK_EVENT_QUEUE
